/**
 * @Project : algorithm-learning
 * @Author : Ruoyu Wang
 * @User : Momenta
 * @DateTime : 2024/3/20 18:50
 */

//现在有一个城市销售经理，需要从公司出发，去拜访市内的某位商家
//已知他的位置以及商家的位置，但是由于城市道路交通的原因，他每次移动只能在左右中选择一个方向或在上下中选择一个方向，现在问他有多少种最短方案到达商家地址。
//给定一个地图 CityMap 及它的 行长度 n 和 列长度 m ，其中1代表经理位置， 2 代表商家位置， -1 代表不能经过的地区， 0 代表可以经过的地区
//请返回方案数，保证一定存在合法路径。保证矩阵的长宽都小于等于 10。
//注意：需保证所有方案的距离都是最短的方案
//数据范围： 2<= n,m <=10
//
//例如当输入为[[2,0,0,0],[0,-1,-1,0],[0,-1,1,0],[0,0,0,0]],4,4时，对应的4行4列CityMap如下图所示：
//经理的位置在(2,2)，商家的位置在(0,0)，经分析，经理到达商家地址的最短方案有两种，分别为：
//(2,2)->(2,3)->(1,3)->(0,3)->(0,2)->(0,1)->(0,0)和
//(2,2)->(3,2)->(3,1)->(3,0)->(2,0)->(1,0)->(0,0)，所以对应的返回值为2
//
//示例 1
//输入
//[[0,1,0],[2,0,0]],2,3
//输出
//2
//
//示例 2
//输入
//[[2,0,0,0],[0,-1,-1,0],[0,-1,1,0],[0,0,0,0]],4,4
//输出
//2

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int steps[20][20];
bool st[20][20];
int res = 0;

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param CityMap int整型vector<vector<>>
     * @param n int整型
     * @param m int整型
     * @return int整型
     */

    int countPath(vector<vector<int>> &cityMap, int m, int n) {
        int mindis;
        int x1, y1, x2, y2;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (cityMap[i][j] == 1) {
                    x1 = i;
                    y1 = j;
                } else if (cityMap[i][j] == 2) {
                    x2 = i;
                    y2 = j;
                }
            }
        }

        // bfs求1到2的最短距离
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                st[i][j] = false;
            }
        }
        queue<vector<int>> q;
        q.push({x1, y1, 0});
        st[x1][y1] = true;
        while (!q.empty()) {
            vector<int> node = q.front();
            q.pop();
            steps[node[0]][node[1]] += node[2];
            for (int i = 0; i < 4; ++i) {
                int x = node[0] + dx[i];
                int y = node[1] + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n && !st[x][y] && cityMap[x][y] != -1) {
                    q.push({x, y, node[2] + 1});
                    st[x][y] = true;
                }
            }
        }
        // bfs求2到1的最短距离
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                st[i][j] = false;
            }
        }
        q.push({x2, y2, 0});
        st[x2][y2] = true;
        while (!q.empty()) {
            vector<int> node = q.front();
            q.pop();
            steps[node[0]][node[1]] += node[2];
            for (int i = 0; i < 4; ++i) {
                int x = node[0] + dx[i];
                int y = node[1] + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n && !st[x][y] && cityMap[x][y] != -1) {
                    q.push({x, y, node[2] + 1});
                    st[x][y] = true;
                }
            }
        }

        //steps表示所有点到1和2的最小距离之和
//        for (int i = 0; i < m; ++i) {
//            for (int j = 0; j < n; ++j) {
//                printf("%d ", steps[i][j]);
//            }
//            puts("");
//        }
//        puts("");

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                st[i][j] = false;
            }
        }

        //dfs求最短路径 steps用于剪枝
        dfs(x1, y1, x2, y2, cityMap, 0);

        return res;
    }

    void dfs(int x1, int y1, int x2, int y2, vector<vector<int>> &cityMap, int step) {
        st[x1][y1] = true;
        if (x1 == x2 && y1 == y2) {
            if (step == steps[x1][y1]) res++;
        } else {
            for (int i = 0; i < 4; ++i) {
                int x = x1 + dx[i];
                int y = y1 + dy[i];
                if (x >= 0 && x < cityMap.size() && y >= 0 && y < cityMap[0].size() && cityMap[x][y] != -1 &&
                    !st[x][y] && steps[x][y] == steps[x1][y1]) {
                    dfs(x, y, x2, y2, cityMap, step + 1);
                }
            }
        }
        st[x1][y1] = false;
    }
};

int main() {
    Solution sl;
    vector<vector<int>> CityMap = {{2, 0,  0,  0},
                                   {0, -1, -1, 0},
                                   {0, -1, 1,  0},
                                   {0, 0,  0,  0}};
    int m = 4;
    int n = 4;
    printf("%d", sl.countPath(CityMap, m, n));
    return 0;
}